#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct LNode
{
    ElemType data;
    struct LNode*next;
}LNode, *LinkList;

//按位序插入
//在第i个位置插入元素e(带头结点)
//bool ListInsert(LinkList &L, int i, ElemType e)
//{
//    if(i<1)
//        return false;
//    LNode *p;
//    int j =0;
//    p= L;
//    while(p!=NULL && j<i-1)
//    {
//        p=p->next;
//        j++;
//    }
//    if(p==NULL)
//        return false;
//    LNode*s = (LNode*)malloc(sizeof(LNode));
//    s->data=e;
//    s->next=p->next;
//    p->next=s;
//    return true;
//}

//在第i个位置插入元素e(不带头结点)
bool ListInsert(LinkList& L, int i, ElemType e)
{
    if(i<1)
        return false;
    if(i==1)
    {
        LNode *s=(LNode*)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;//头指针指向新节点
        return true;
    }
    LNode *p;
    int j =1;
    p = L;
    while(p!=NULL && j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    LNode*s = (LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

//制定节点的后插操作
bool InsertNextNode(LNode* p,ElemType e)
{
    if(p==NULL)
        return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    if(s==NULL)
        return false;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;

}

////在第i个位置插入元素e(不带头结点)
//bool ListInsert(LinkList& L, int i, ElemType e)
//{
//    if(i<1)
//        return false;
//    if(i==1)
//    {
//        LNode *s=(LNode*)malloc(sizeof(LNode));
//        s->data=e;
//        s->next=L;
//        L=s;//头指针指向新节点
//        return true;
//    }
//    LNode *p;
//    int j =1;
//    p = L;
//    while(p!=NULL && j<i-1)
//    {
//        p=p->next;
//        j++;
//    }
//    return InsertNextNode(p,e);
//}

//前插操作：在p节点之前插入元素e
bool InsertPriorNode(LNode* p, ElemType e)
{
    if(p==NULL)
        return false;
    LNode *s=  (LNode*)malloc(sizeof(LNode));
    if(s==NULL)
    {
        return false;
    }
    s->next=p->next;
    p->next=s;   //新节点s连到p之后
    s->data=p->data; //将p中元素复制到s中
    p->data=e; //p中元素覆盖到e
    return true;

}

//按位序删除（带头节点）
//ListDelete(&L,i,&e);

bool ListDelete(LinkList& L, int i, ElemType& e)
{
    if(i<1)
        return false;
    LNode* p;
    int j =0;
    p = L;
    while(p!=NULL && j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)
        return false;
    if(p->next==NULL)
        return false;
    LNode* q=p->next;
    e = q->data;
    p->next=q->next;
    free(q);
    q=NULL;
    return true;
}

//指定节点的删除

//删除指定节点p
bool DeleteNode(LNode* p)
{
    if(p==NULL)
        return false;
    LNode* q=p->next;     //令q指向*p的后继结点
    p->data=p->next->data;//和后继节点交换数据域
    p->next=q->next;       //将*q节点从链中“断开”
    free(q);       //释放后继结点的存储空间
    return true;
}

